////////////////////////////////////////////////////////////////////////////////////////////////////
/// Copyright (c) 2009 - 2010 RacoonStudios
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of this
/// software and associated documentation files (the "Software"), to deal in the Software
/// without restriction, including without limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
/// to whom the Software is furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all copies or
/// substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
/// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
/// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
/// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef hashtable_h__
#define hashtable_h__

#include "core/types.h"
#include "helper/array.h"
#include "helper/fixedarray.h"
#include "helper/keyvaluepair.h"

namespace Helper
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	/// \class	HashTable
	///
	/// \brief	Here we are using seperate chaining.
	///			We have a constant size for the HashTable itself but its addresses can carry
	///			every amount of files with the specified index.
	///
	/// \author	khaos
	/// \date	12.12.2009
	////////////////////////////////////////////////////////////////////////////////////////////////////
	template<class K, class V>
	class HashTable
	{
		public:

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	public: HashTable()
			///
			/// \brief	Hash table. 
			///
			/// \author	khaos
			/// \date	05.01.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			HashTable();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	HashTable(tSize size)
			///
			/// \brief	Constructor. 
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	size	The size the HashTable should have. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			HashTable(tSize size);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	HashTable(const HashTable<K,V> & rhs)
			///
			/// \brief	Constructor. 
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	rhs		The right hand side object. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			HashTable(const HashTable<K,V> & rhs);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void operator= (const HashTable<K,V> & rhs)
			///
			/// \brief	Copy operator. 
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	rhs	The right hand side object. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void operator = (const HashTable<K,V> & rhs);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	const V & operator[] (const K & key) const
			///
			/// \brief	 casting operator. 
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	key	The key. 
			///
			/// \return	The value belonging to the specified key.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			const V & operator [] (const K & key) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	V & operator[] (const K & key)
			///
			/// \brief	Casting operator. 
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	key	The key. 
			///
			/// \return	The value belonging to the specified key.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			V & operator [] (const K & key);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	tSize Size() const
			///
			/// \brief	Returns the size of this HashTable.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \return	The size of the HashTable.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			tSize Size() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Clear()
			///
			/// \brief	Clears the whole HashTable and all registers.
			///
			/// \author	Markus
			/// \date	30.01.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Clear();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	tSize Capacity() const
			///
			/// \brief	Returns the capacity of the HashTable.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \return	The capacity of the HashTable.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			tSize Capacity() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	bool Contains(const K & key) const
			///
			/// \brief	Determines if this HashTable contains the specified key.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	key	The key we are looking for.
			///
			/// \return	True if the specified key is within the HashTable, otherwise false.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			bool Contains(const K & key) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	bool IsEmpty() const
			///
			/// \brief	Determines if this HashTable is empty.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \return	True if this HashTable is empty, otherwise false.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			bool IsEmpty() const;




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Add(const K & key, const V & val)
			///
			/// \brief	Adds the specified key and its belonging value to the HashTable.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	key	The key we want to add. 
			/// \param	[in]	val	The value we want to add. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Add(const K & key, const V & val);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Add(const KeyValuePair<K,V> & kvp)
			///
			/// \brief	Adds the specified KeyValuePair to the HashTable.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	kvp	The KeyValuePair we want to add.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Add(const KeyValuePair<K,V> & kvp);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Erase(const K & key)
			///
			/// \brief	This erases the element specified by the value.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \param	[in]	key	The key of the element we want to erase.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Erase(const K & key);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Array<KeyValuePair<K,V> > Content() const
			///
			/// \brief	Returns an Array with all elements of the HashTable.
			///
			/// \author	khaos
			/// \date	05.01.2010
			///
			/// \return	An Array containing all elements of the HashTable.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Array<KeyValuePair<K,V> > Content() const;

		protected:

			int m_size;

			FixedArray<Array<KeyValuePair<K,V> > > m_hashtable;

		private:

	};





	///
	template<class K, class V>
	inline HashTable<K,V>::HashTable():
	m_hashtable(512),
		m_size(0)
	{

	}


	///
	template<class K, class V>
	inline HashTable<K,V>::HashTable(tSize size):
	m_hashtable(size),
		m_size(0)
	{

	}


	///
	template<class K, class V>
	inline HashTable<K,V>::HashTable(const Helper::HashTable<K,V> & rhs):
	m_hashtable(rhs.m_hashtable),
		m_size(rhs.m_size)
	{

	}



	///
	template<class K, class V>
	inline void HashTable<K,V>::operator =(const Helper::HashTable<K,V> &rhs)
	{
		if(this != &rhs)
		{
			this->m_hashtable = rhs.m_hashtable;

			this->m_size = rhs.m_size;
		}
	}


	///
	template<class K, class V>
	inline const V & HashTable<K,V>::operator [](const K &key) const
	{
		tIndex hashtableindex = key.HashCode() % this->m_hashtable.Size();

		const Array<KeyValuePair<K,V> > & elements = this->m_hashtable[hashtableindex];

		return elements[elements.BinarySearchIndex(key)].Value();
	}


	///
	template<class K, class V>
	inline V & HashTable<K,V>::operator [](const K & key)
	{
		tIndex hashtableindex = key.HashCode() % this->m_hashtable.Size();

		const Array<KeyValuePair<K,V> > & elements = this->m_hashtable[hashtableindex];

		return elements[elements.BinarySeachIndex(key)].Value();
	}





	///
	template<class K, class V>
	inline tSize HashTable<K,V>::Size() const
	{
		return this->m_size;
	}


	///
	template<class K, class V>
	inline void HashTable<K,V>::Clear()
	{
		tIndex size = this->m_hashtable.Size();

		for(tIndex i = 0; i < size; i++)
			this->m_hashtable[i].Clear();

		this->m_size = 0;
	}


	///
	template<class K, class V>
	inline tSize HashTable<K,V>::Capacity() const
	{
		return this->m_hashtable.Size();
	}


	///
	template<class K, class V>
	inline bool HashTable<K,V>::IsEmpty() const
	{
		return (this->m_size != 0);
	}


	///
	template<class K, class V>
	inline bool HashTable<K,V>::Contains(const K & key) const
	{
		if(this->m_size < 0)
			return false;

		tIndex hashtableindex = key.HashCode() % this->m_hashtable.Size();

		Array<KeyValuePair<K,V> > elements = this->m_hashtable[hashtableindex];

		return (InvalidIndex != elements.BinarySearchIndex(key));
	}





	///
	template<class K, class V>
	inline void HashTable<K,V>::Add(const Helper::KeyValuePair<K,V> &kvp)
	{
		tIndex hashtableindex = kvp.Key().HashCode() % this->m_hashtable.Size();

		this->m_hashtable[hashtableindex].Add(kvp);

		this->m_hashtable[hashtableindex].Sort();

		++this->m_size;
	}


	///
	template<class K, class V>
	inline void HashTable<K,V>::Add(const K &key, const V &val)
	{
		Helper::KeyValuePair<K,V> temp(key, val);

		this->Add(temp);
	}


	///
	template<class K, class V>
	inline void HashTable<K,V>::Erase(const K &key)
	{
		tIndex hashtableindex = key.HashCode() % this->m_hashtable.Size();

		Array<KeyValuePair<K,V> > elements = this->m_hashtable[hashtableindex];

		elements.EraseIndex(elements.BinarySearchIndex(key));
	}


	///
	template<class K, class V>
	inline typename Array<KeyValuePair<K,V> > HashTable<K,V>::Content() const
	{
		Array<KeyValuePair<K,V> > result;

		int num = this->m_hashtable.Size();

		for(int i = 0; i < num; i++)
		{
			if(this->m_hashtable[i].Size() > 0)
				result.Add(this->m_hashtable[i]);
		}

		return result;
	}

}

#endif // hashtable_h__